﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace TreeDemo
{
    class TreeHelper
    {
        #region Print Tree
        public static void PrintTree(BinarySearchTreeNode node)
        {
            int h = GetHeight(node);
            int rows = (h * (h + 1)) / 2;
            int cols = 2 * rows - 1;

            treeMatrix = new string[rows, cols];

            for (int i = 0; i < rows; i++)
                for (int j = 0; j < cols; j++)
                    treeMatrix[i, j] = " ";

            Print(node, 0, (h * h + h - 2) / 2);

            for (int i = 0; i < rows; i++)
            {
                for (int j = 0; j < cols; j++)
                    Console.Write(treeMatrix[i, j]);
                Console.WriteLine();
            }
        }

        private static void Print(BinarySearchTreeNode node, int row, int col)
        {
            if (node == null) return;
            int i;
            treeMatrix[row, col] = node.data.ToString();
            int height = GetHeight(node);
            for (i = 1; i < height; i++)
            {
                if (node.left != null)
                    treeMatrix[row + i, col - i] = "/";
                if (node.right != null)
                    treeMatrix[row + i, col + i] = @"\";
            }
            Print(node.left, height + row, col - i);
            Print(node.right, height + row, col + i);
        }

        private static string[,] treeMatrix;

        private static int GetHeight(BinarySearchTreeNode node)
        {
            if (node == null)
                return 0;

            else
            {
                int leftIndex = GetHeight(node.left) + 1;
                int rightIndex = GetHeight(node.right) + 1;
                return Math.Max(leftIndex, rightIndex);
            }
        }
        #endregion

        #region Is Tree Balanced
        public static bool IsTreeBalanced(BinarySearchTreeNode node)
        {
            ScanBalancing(node);

            return unBalancedNodesCount == 0;
        }

        static int unBalancedNodesCount = 0;

        private static int ScanBalancing(BinarySearchTreeNode node)
        {
            if (node == null)
                return 0;

            else
            {
                int leftIndex = ScanBalancing(node.left) + 1;
                int rightIndex = ScanBalancing(node.right) + 1;

                if (Math.Abs(leftIndex - rightIndex) > 1)
                {
                    unBalancedNodesCount++;
                    node.balanced = false;
                    //Console.WriteLine("Tree is not balanced at node: " + node.data);
                }
                return Math.Max(leftIndex, rightIndex);
            }
        }
        #endregion

        #region Mirror Tree
        public static BinarySearchTreeNode CreateMirror(BinarySearchTreeNode rootNode)
        {
            CreateMirrorTree(rootNode, mirrorRootNode);
            return mirrorRootNode;
        }

        static BinarySearchTreeNode mirrorRootNode;
        private static BinarySearchTreeNode CreateMirrorTree(BinarySearchTreeNode node1, BinarySearchTreeNode node2)
        {
            if (node1 == null)
                return null;

            node2 = new BinarySearchTreeNode(node1.data);
            if (mirrorRootNode == null) mirrorRootNode = node2;

            node2.right = CreateMirrorTree(node1.left, node2.left);
            node2.left = CreateMirrorTree(node1.right, node2.right);

            return node2;
        }
        #endregion

        #region Breath wise Lists
        public static List<List<BinarySearchTreeNode>> CreateDepthWiseLists(BinarySearchTreeNode rootNode)
        {
            List<List<BinarySearchTreeNode>> nodeListCollection = new List<List<BinarySearchTreeNode>>();
            List<BinarySearchTreeNode> nodeList = new List<BinarySearchTreeNode>();
            nodeList.Add(rootNode);
            nodeListCollection.Add(nodeList);

            while (true)
            {
                List<BinarySearchTreeNode> nList = new List<BinarySearchTreeNode>();
                foreach (var node in nodeList)
                {
                    if (node.left != null)
                        nList.Add(node.left);
                    if (node.right != null)
                        nList.Add(node.right);
                }
                if (nList.Count == 0)
                    break;
                nodeListCollection.Add(nList);
                nodeList = nList;
            }

            return nodeListCollection;
        }
        #endregion

        #region Common Ancestor
        internal static BinarySearchTreeNode FindFirstCommonAncestor(BinarySearchTreeNode node, int val1, int val2)
        {
            if (PresentIn(node.left, val1) && PresentIn(node.left, val2))
                return FindFirstCommonAncestor(node.left, val1, val2);

            else if (PresentIn(node.right, val1) && PresentIn(node.right, val2))
                return FindFirstCommonAncestor(node.right, val1, val2);

            return node;
        }

        private static bool PresentIn(BinarySearchTreeNode nd, int val)
        {
            if (nd == null)
                return false;
            if (nd.data == val)
                return true;
            return PresentIn(nd.left, val) || PresentIn(nd.right, val);
        }
        #endregion

        #region Find Nearest Node
        public static BinarySearchTreeNode FindNearestNode(BinarySearchTreeNode node, BinarySearchTreeNode parent, int val)
        {
            if (node == null)
                return null;
            if (node.data == val)
                return NearestChild(node, parent, val);

            BinarySearchTreeNode nearestNode = FindNearestNode(node.left, node, val);
            if (nearestNode == null)
                nearestNode = FindNearestNode(node.right, node, val);

            if (nearestNode != null)
                if (Math.Abs(nearestNode.data - val) > Math.Abs(node.data - val))
                    nearestNode = node;
            return nearestNode;
        }

        private static BinarySearchTreeNode NearestChild(BinarySearchTreeNode node, BinarySearchTreeNode parent, int val)
        {
            BinarySearchTreeNode nearest = null;
            BinarySearchTreeNode temp;
            if (parent != null)
            {
                nearest = parent;
                if ((temp = RightMostOf(node.left)) != null)
                {
                    if (Math.Abs(nearest.data - val) > Math.Abs(temp.data - val))
                        nearest = temp;
                }
                if ((temp = LeftMostOf(node.right)) != null)
                {
                    if (Math.Abs(nearest.data - val) > Math.Abs(temp.data - val))
                        nearest = temp;
                }
            }
            else if (node.left != null)
            {
                nearest = RightMostOf(node.left);
                if (node.right != null)
                {
                    temp = LeftMostOf(node.right);
                    if (Math.Abs(nearest.data - val) > Math.Abs(temp.data - val))
                        nearest = temp;
                }
            }
            else
            {
                nearest = LeftMostOf(node.right);
            }
            return nearest;
        }

        private static BinarySearchTreeNode LeftMostOf(BinarySearchTreeNode node)
        {
            if (node != null)
            {
                BinarySearchTreeNode temp = node;
                while (temp.left != null)
                    temp = temp.left;

                return temp;
            }
            return null;
        }

        private static BinarySearchTreeNode RightMostOf(BinarySearchTreeNode node)
        {
            if (node != null)
            {
                BinarySearchTreeNode temp = node;
                while (temp.right != null)
                    temp = temp.right;
                return temp;
            }
            return null;
        }
        #endregion

        #region All Paths to given value
        public static void AllPathsToGivenValue(BinarySearchTreeNode node, int sum, int level, ArrayList nodeList)
        {
            if (node == null)
                return;
            nodeList.Add(node.data);
            int temp = 0;
            for (int i = level; i >= 0; i--)
            {
                temp += (int)nodeList[i];
                if (temp == sum)
                    PrintPath(i, level, nodeList);
            }
            ArrayList nodeList1 = (ArrayList)nodeList.Clone();
            ArrayList nodeList2 = (ArrayList)nodeList.Clone();

            AllPathsToGivenValue(node.left, sum, level + 1, nodeList1);
            AllPathsToGivenValue(node.right, sum, level + 1, nodeList2);
        }

        private static void PrintPath(int index, int level, ArrayList nodeList)
        {
            for (var i = index; i <= level; i++)
                Console.Write(nodeList[i] + " ");
            Console.WriteLine();
        }
        #endregion

        #region Find Distance from root node
        static bool found = false;
        internal static int FindDistanceFromRootNode(BinarySearchTreeNode node, int p, int q)
        {
            return FindDistanceFromRootNode(node, p) + FindDistanceFromRootNode(node, q);
        }
        internal static int FindDistanceFromRootNode(BinarySearchTreeNode node, int p)
        {
            int left = 0, right = 0;
            if (node == null)
                return -1;

            if (node.data == p)
            {
                found = true;
                return 0;
            }

            if (node.right == null && node.left == null)
                return -1;


            right = FindDistanceFromRootNode(node.right, p) + 1;
            if (!found)
            {
                right = 0;
                left = FindDistanceFromRootNode(node.left, p) + 1;
                if (!found)
                    left = 0;
            }

            return left + right;
        }
        #endregion

        #region Replace With Sum of childs and self
        internal static int ReplaceWithSum(BinarySearchTreeNode node)
        {
            if (node == null)
                return 0;
            int leftSum = ReplaceWithSum(node.left);
            int rightSum = ReplaceWithSum(node.right);

            node.data += leftSum + rightSum;
            return node.data;
        }
        #endregion

        static int index = 0; //These will initialize to zero only once as its static
        public static void printNthNode(BinarySearchTreeNode root, int N)
        {
            if(root == null)
            return;

            

            //For every Node go to the right of that node first.
            printNthNode(root.right, N);


            //Right has returned and now current node will be greatest
            if(++index == N)
            {
                Console.WriteLine(root.data);
                return;
            }

            //And at last go to the left
            printNthNode(root.left, N);
        }

        static Stack<int> q = new Stack<int>();
        public static string PrintAllPaths(BinarySearchTreeNode node)
        {
            if (node == null)
                return null;
            q.Push(node.data);
            var left = PrintAllPaths(node.left);
            var right = PrintAllPaths(node.right);
            if (left == null && right == null)
            {
                foreach (var item in q.Reverse())
	            {
		            Console.Write(item + " ");
	            }
            }
            q.Pop();            
            Console.WriteLine();
            return node.data.ToString();
        }
    }
}
